Methods for generating tests for logic circuits to detect faults therein are well known in the art. Most of these prior methods use the so-called "stuck-at" fault model and are based on path-sensitization. See, for example, J.P. Roth "Diagnosis of Automated Failures: A Calculus and A Method", IBM Journal of Research and Development, No. 10, October 1966, pp. 278-281; P. Goel, "An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits", IEEE Transactions on Computers, Vol. C-30, March 1981, pp. 215-222; and H. Fujiwara and T. Shimono, "On the Acceleration of Test Generation Algorithms", IEEE Transactions on Computers, Vol. C-32, December 1983, pp. 1137-1144.
In general, the three steps involved in a pathsensitization algorithm are:
1. Specification of inputs to generate the appropriate value at the site of the fault (0 for stuck-at-1 fault and 1 for a stuck-at-0 fault). This step is called fault sensitization.
2. Selection of a path from the fault site to an output and specification of additional signal values to propagate the fault along the path to the output. This step is called error propagation.
3. Specification of input values to produce the signal values specified in step 2. This step is called line justification.
See M.A. Breuer and A.D. Friedman, Diagnosis and Reliable Design of Digital Systems, Computer Science Press, 1976, p. 37.
The prior art methods are suitable for generating tests for general combinational logic circuits that are composed of arbitrary interconnection of logic circuits. As a result, the algorithms are complex and difficult to implement.
For certain types of applications, such as Programable Logic Arrays (PLA), where the logic circuits comprise an array of a first type of logic circuits interconnected with an array of a second type of logic circuits and have a well defined interconnection, the method for generating tests for the combinational logic circuits can be greatly simplified.